package shares

/*
时间复杂度:O(N)
空间复杂度:O(N)
*/

func maxProfit(prices []int, fee int) int {
	buy := make([]int, len(prices))
	sell := make([]int, len(prices))
	buy[0], sell[0] = -prices[0], 0
	for i := 1; i < len(prices); i++ {
		buy[i] = Max(buy[i-1], sell[i-1]-prices[i])
		sell[i] = Max(sell[i-1], buy[i-1]+prices[i]-fee)
	}
	return sell[len(prices)-1]
}


/*
时间复杂度:O(N)
空间复杂度:O(1)
*/

func maxProfit1(prices []int, fee int) int {
	buy, sell := -prices[0], 0
	for i := 1; i < len(prices); i++ {
		buy = Max(buy, sell-prices[i])
		// 这里的buy已经是buy[i]了，不是buy[i-1];为什么还能dp成功??
		// 因为buy[i] = Max(buy[i-1], sell[i-1]-prices[i])这一步，有两种可能
		// 1.buy[i] = buy[i-1], 则下面是用的buy就还是buy[i-1]，成立
		// 2.buy[i] = sell[i-1]-prices[i], 下面的buy+prices[i]-fee就相当于 对第i件物品买了之后又卖出了,也是成立的
		sell = Max(sell, buy+prices[i]-fee)
	}
	return sell
}